Configurable integrated circuits differ from application specific integrated circuits (ASICs) in that a single underlying integrated circuit can be used to implement a variety of complex digital logic circuits by programming or configuring the underlying integrated circuit. As such, they have many applications and are less expensive to design and manufacture, except at extremely high volumes.
Field programmable gate arrays (FPGAs), mask programmable gate arrays (MPGAs), multi-processors for parallel computing, and system-on-chip integrated circuits (SOCs) are examples of configurable integrated circuits. Field programmable gate arrays are programmable in the field by the user while mask programmable gate arrays are programmable during manufacturing. A field or mask programmable gate array typically contains an array of modularized logic cells and signal routing resources where the routing resources can be configured or programmed to interconnect the logic cells to implement a variety of logic functions. In a multi-processor for parallel computing, either on a single chip or by linking multiple chips, the network of routing resources forms a routing architecture that routes data between the processors, depending on the logic design implemented and how the processors are scheduled. The interconnections between the processors, memories, and peripheral elements in a “system-on-chip” can be changed depending on the demands of the program that is running.
In general, configurable integrated circuits for devices such as field or mask programmable gate arrays comprise of logic or other functional cells that can be interconnected with each other with routing resources thus allowing for the transmission of signals within the integrated circuit. These logic or other functional cells shall be referred to herein generally as resources. The signal outputs, or drivers in said circuits can then be designed or programmed, via the selection of interconnect resources, to be interconnected to a set of one or more signal inputs or targets that are base resources to create a set of signal nets in order to implement a specific logic function.
Routing resources can be interconnect resources or switching resources. Interconnect resources can be wires, waveguides, or other channels designed to carry signals. Switching resources can be switches or multiplexers. A multiplexer is a switch that allows one to choose among a variety of detailed point to point signal routing paths, analogous to a track switch on a section of a railroad. Multiplexers are typically interconnected to base resources or other multiplexers by other interconnect resources such as wires and vias.
The basic structure of a traditional configurable integrated structure has a routing architecture that comprises of a two-dimensional array of logic cells connected with interconnecting resources in the form of a mesh. [“Flexibility of Interconnection Structures for Field Programmable Gate Arrays”, J. Rose and S. Brown, IEEE Journal of Solid-State Circuits, vol. 26, no. 3, Mar. 1991. See also, Field Programmable Gate Arrays, Brown et al., page 4-5, Kluwer Academic Publishers, 1992.] Typically, the logic cells in field programmable gate arrays are arranged in a two-dimensional array or “mesh”, comprising of a plurality of rows and columns of logic cells. One general example of such an integrated circuit is illustrated by the basic array structure in FIG. 1 where horizontal and vertical routing resources, typically wires and switches, occupy the area (112) between the rows and columns of the logic cells or base resources (111) and interconnect these cells. Input/output devices (IOs) are located at the periphery (113) of the array to propagate signals into and out of the field programmable gate array. Routing resources also directly interconnect each logic cell with the logic cells above and below and to either side of the logic cell. These routing resources enable the signal propagation between the logic cells.
Another variation of an integrated circuit with a mesh interconnect routing architecture is illustrated in FIG. 1b. In this example, input/output devices (113) are again located at the periphery of the array while the logic cells (111) are not only directly interconnected to their immediate logic cell neighbors horizontally and vertically but also diagonally by routing resources (112). This diagonal connectivity can be strictly logical in which case the actual physical routes would still comprise of horizontal and vertical rows, with a right angle “bend” at the physical chip-layout level.
Two critical factors can affect the cost and performance of an integrated circuit. The first is the speed at which a signal can propagate through that circuit. The second is the total amount of physical space needed to implement a particular logic function. One disadvantage of mesh arrays, such as those illustrated in FIG. 1a, is that the horizontal and vertical routing resources may occupy more than 95 percent of the chip area, i.e., the area of the integrated circuit. The large amount of chip area dedicated to the routing resources reduces the amount of chip area available for the base cells, thus reducing the complexity of digital logic circuits that can be implemented for a given device size. Since many digital logic circuits are modular, needing mainly local routing resources between cells, they do not need the general point-to-point interconnectivity, routing resources, and the physical space they occupy, are wasted.
Recently, integrated circuits with hierarchical interconnect routing architectures that reduce the amount of integrated chip space needed to implement logic functions while maintaining signal propagation speed have been proposed. [U.S. Pat. No. 6,940,308 proposed integrated circuits with a hierarchical interconnect routing architecture based upon Benes networks.] United States Patent Application No. 20030039262 proposed a multiplexer-based integrated circuit with a hierarchical interconnect routing architecture. In general, the hierarchical interconnect routing architectures of these integrated circuits can be mapped to a graph theoretic tree where interconnect resources such as wires and wave guides are mapped to the edges of the tree and switching resources and base resources are mapped to the nodes of the tree at the various levels of the tree hierarchy. Typically, the base resources such as logic cells are interconnected to the routing network at the lowest level of the tree. Switching resources at a particular level are interconnected to switching resources and base resources at the next lower or higher level by interconnect resources.
FIG. 2a illustrates the logical interconnections for a quadtree an example of an integrated circuit whose basic connectivity has a hierarchical interconnect routing architecture. This basic unit for the first two levels of the quadtree will also be referred to herein as a two level subtree. For this two level subtree, the interconnect resources (213) interconnect four base resources (211) at the first level to the switching resources (212) at the second level. For an integrated circuit with a quadtree structure having more than two levels, switching resources at the next higher are not shown in this Figure.
FIG. 2b illustrates a possible physical layout of this two level subtree. The four base resources (211) are interconnected to the next level of the hierarchy by routing resources (214) that include switching resources and interconnect resources. Each switching resource at a level is interconnected directly by interconnect resources to other switching resources at the next higher and/or lower level.
FIG. 3a illustrates the logical interconnections for a quadtree containing the first three levels of a quadtree. The interconnect resources (213) of this three level subtree interconnect four two level subtrees as illustrated by FIG. 2a to switching resources (212) at the third level. As shown in FIG. 3b, this three level quadtree can also be represented as four second level subtrees (215) as indicated in FIG. 3a that are hierarchically interconnected by interconnect resources (213) with switching resources on the third level (212). In this case, the branching factor of the tree is the same at each level. That is, the tree is “self-similar.” However, other kinds of branching schemes, such as a “K-ary” tree can be accommodated in the same kind of framework.
FIGS. 3c and 3d illustrate a physical layout of this three level quadtree where routing resources (214) interconnect four second level subtrees with switching resources at the third level. This three level quadtree can also be represented as four second level subtrees (215) as indicated in FIG. 3a that are hierarchically interconnected by routing resources (214) with the switching resource on the third level (212).
Continuing this pattern, FIG. 4a illustrates the logic interconnections for the first four levels of a quadtree. Again, the interconnect resources (213) interconnect four three level subtrees (216) to switching resources (212) at the fourth level. Each three level subtrees (216) have four two level quadtrees (215) that hierarchically interconnect switching resources at the second level to the base resources at the first level. As shown in FIG. 4b, this four level quadtree can also be represented as four three level subtrees (216).
FIGS. 4c and 4d illustrate a possible physical layout of this four level quadtree where routing resources (214) interconnect four of three level subtrees as illustrated by FIG. 3a with switching resources at the fourth level. This four level quadtree can also be represented as four, third level subtrees (216) that are hierarchically interconnected by routing resources (214) with switching resources on the fourth level (212).
Following this formula, a quadtree of any number of levels can be built where, at the Nth level, interconnect resources interconnect the four (N−1)th subtree to switching resources at the Nth level and switching resources at the Nth level.
Using such an algorithm or a generalization thereof, an integrated circuit with a hierarchical interconnect routing architecture of any number of levels can be built where each level can contain a variety of subtrees and interconnect resources interconnect switching and base resources at a level with the subtrees at a lower level and switching and base resources at a higher level.
Integrated circuits with hierarchical interconnect routing architectures have many advantages. They allow for the use of subtrees as building blocks that can be assembled with a straightforward automated algorithm for arbitrary network sizes. Therefore, the design of this type of integrated circuit can be conducted with an automatic software generator that allows a user to specify the size of the integrated circuit.
Integrated circuits with hierarchical interconnect routing architecture are also highly scalable. As the number of base resources in an integrated circuit grows, the interconnection demands generally grow super-linearly. For integrated circuits with hierarchical interconnect routing architecture such as the quadtree described above, as the number of base resources grow, only the higher levels of the hierarchy need to expand while the lower levels remain the same. In contrast, in an integrated circuit with a mesh or planar interconnect routing architecture, every switching resource has to be expanded to accommodate the increased demands for routing resulting from an increase in the number of base resource.
However, there are also drawbacks. In an integrated circuit with hierarchical interconnect routing architecture, even though a base or switching resource may be physically placed close to another base or switching resource, they may be logically far apart if they belong to different subtrees at a level. For example, in FIG. 5, redrawn from the same hierarchical interconnect routing architecture in FIG. 3a, the base resources (517) and (518) from different subtrees may be physically next to each other but belong to a different subtrees, therefore, in order for a signal to travel from (517) to (518), the signal has to travel from the base resource in the first level, through the switching resources (504), (501), and (505) in second and third levels to reach base resource (518). Since signal speed is critical in some applications, an integrated circuit with a hierarchical interconnect routing architecture may be less desirable than one with a mesh interconnect routing architecture because of the potentially long distance that a signal may have to travel to reach its physical neighbor.
Due to the limitations of the prior art, it is therefore desirable to have methods for interconnecting resources in integrated circuits and integrated circuits with interconnect architectures that has the advantages of both mesh interconnect routing architectures and hierarchical interconnect routing architectures.